1. Field of the Invention
The present invention relates to the field of telecommunications. More particularly, the present invention relates to a method for fairly allocating link bandwidth for Available Bit Rate (ABR) service in Asynchronous Transfer Mode (ATM) networks.
2. Description of the Related Art
The emergence of ATM (Asynchronous Transfer Mode) technology in communication networks is an imminent avenue for various multimedia applications. As an established principle, ATM provides flexibility for integrating transport of different classes of traffic, with different classes having a wide ranges of service requirements. Most data applications cannot predict their own traffic parameters and, accordingly, usually require a service that dynamically shares available bandwidth with other data applications. Such a service is referred to as an Available Bit Rate (ABR) service. Requirements for an ABR service are disclosed by The ATM Forum, "The ATM Forum Traffic Management Specification, Version 4.0," ATM Forum Contribution, 1995, incorporated by reference herein.
Because of the bursty nature of ATM communications, ABR service congestion control poses many challenging problems and is the focus of recent standardization efforts of the ATM Forum. The ATM Forum has adopted a rate-based congestion control approach without making commitments to any particular switch algorithm. The rate-based approach provides architectural flexibility with a wide range of possible switch implementations covering varying degrees of cost and complexity. The network switch is responsible for allocating a fair share of the available bandwidth among all competing connections at this switch point. This is accomplished by implementing a fair rate allocation scheme.
Some key issues that a rate allocation scheme must address are fairness, efficiency, responsiveness, robustness, scalability, stability, complexity and inter-operability. Regarding fairness, some type of a fairness criteria should be guaranteed for all connections, especially for a start-up VC connection which has difficulty obtaining bandwidth from existing VC connections. A scheme should be efficient by producing high effective throughput, high link utilization and low buffer usage, and should respond and adapt rapidly to changes in available bandwidth. Bit rates should converge to the max-min fair allocations quickly when new connections are formed or old connections exit. The scheme should be robust so that any loss or mis-tuning of parameters does not cause the network to fail. The scheme should scale well with the number of connections in the network, time. length of connections, propagation delays in the network, etc. At steady-state, the scheme should be stable by maintaining rates and does not cause large oscillations leading to an unstable network. The scheme should be simple to implement without adding significant cost to switch design. Required computations should be kept to a minimum. Lastly, the switches on which the scheme is provided should be able to operate effectively with existing simpler switches.
A primary goal of an ABR service is to utilize the network resources to their fullest extent while maintaining some notion of fairness among competing ABR connections. The ATM Forum has accepted the notion of max-min fairness, as disclosed by J. M. Jaffe, "Bottleneck Flow Control," IEEE Transactions on Communications, vol. 29, pp. 954-962, July 1981, and incorporated by reference herein, as the criterion for deciding fairness among ABR service users in an ATM network. The max-min fairness criterion provides the maximum possible bandwidth to the source receiving the least bandwidth among all contending sources.
To formulate the problem of fairness as it relates to an ABR service, let L define the set of links and S define the set of virtual connections established in a given ATM network. Each session j.di-elect cons.S has a fixed path and traverses a subset of links L.sub.j. Let S.sub.t denote the set of sessions that traverse link 1.di-elect cons.L. The capacity (or bandwidth) of each link 1.di-elect cons.L is denoted by C.sub.l. Let .lambda..sub.j.sup.CCR denote the allocated rate at which the cells of session j enters the network (i.e., current cell rate), and let .lambda..sub.j.sup.ER denote the maximum permitted transmission rate of session j (i.e., explicit rate).
Let .lambda..sub.j be the allocated rate for session j. The flow on link 1, F.sub.l is defined as: ##EQU1##
A link 1.di-elect cons.L is defined to be the "bottleneck link" for a session j, if F.sub.l =C.sub.l, and .lambda..sub.j is at least as large as the rate of any other sessions using the bottleneck link. The rate, .lambda..sub.j, is referred to as the bottleneck bandwidth for the session j.
The ABR max-min principle is fair since all sessions sharing a link receive an equal share of bandwidth of the link provided that each session can use the fair share, and the only factor preventing a source from obtaining a higher allocation is a bottleneck link. Moreover, the max-min principle is efficient in the sense that it maximizes the throughput.
Congestion control for an ABR service is based on a per-connection control using feedback information from a network for controlling the rate at which a source transmits cells for each virtual connection (VC). The basic element of the control is to provide a proportional rate adjustment, where any increase or decrease in a source rate is proportional to the current rate of the source. Communication of congestion and rate allocation information is done via special control cells called Resource Management (RM) cells. The basic option offered by ATM switches consists of a single-bit binary feedback, supported by EFCI (Explicit Forward Congestion Indication) mechanisms provided in the switches, and a Congestion Indication (CI) bit and a No Increase (NI) bit contained in the RM cells.
A flexibility of the rate-based congestion control approach is a calculation of explicit cell transmission rates for ABR service users by switches. Since many ABR service users compete for bandwidth, the available bandwidth must be shared fairly among all ABR service users. To achieve "fairness", each switch in an ATM network executes a rate allocation algorithm. The challenge is to calculate the explicit rate, which is a fair share of available bandwidth for an ABR service user, in a distributed and asynchronous way.
Binary schemes, however, result in unfairness (i.e., the beat-down problem), and a slow response. To overcome these problems, switches may employ, in addition to binary schemes, sophisticated mechanisms that compute an Explicit Rate (ER) value that is fed back in the ER field of an RM cell. For example, see L. Roberts, "Enhanced PRCA (Proportional Rate-Control Algorithm)," The ATM Forum Contribution No. 94-0735R1, August 1994; R. Jain et al., "The OSU Scheme for Congestion Avoidance using Explicit Rate Indication," tech. rep., Ohio State University, September 1994; A. Charny et al., "Congestion Control with Explicit Rate Indication," Proc. ICC 95, June 1995, which is incorporated by reference herein; and K. Siu et al., "Adaptive Proportional Rate Control for ABR Service in ATM Networks," Tech. Rep. 94-07-01, Electrical and Computer Engineering, University of California, Irvine, July 1994, each of which is incorporated by reference herein. The more advanced approaches require switches that compute the fair share for each connection and explicitly set the source transmission rate.
The ATM Forum defined standards for behavior of a source, a destination and switch are set forth in The ATM Forum, "The ATM Forum Traffic Management Specification, Version 4.0," ATM Forum Contribution, 1995. The general end-to-end control mechanism is depicted in FIG. 1. In FIG. 1, a source 10 transmits data cells 11 in a forward direction through ATM switches 12 to a destination 13. Once a connection has been set up between source 10 and destination 13 and source 10 has received permission to transmit, source 10 sends data cells 11 at an Initial Cell Rate (ICR). For each connection, the source end system 10 generates one forward RM 14 cell for every N.sub.RM data cell. Upon generation of an RM cell, source 10 sets its current Allowed Cell Rate (ACR) on one of the RM cell fields called the Current Cell Rate (CCR). Additionally, the ER field of the RM cell is set to the Peak Cell Rate (PCR) of the connection. When an RM cell is received at a switch 12, the switch processes the congestion information, and marks the appropriate RM cell fields based on the switch behavior. When the RM 14 cell reaches the destination end system 13, the RM cell is returned to source 10 by destination end system 13, creating a backward flow of RM cells to close the feedback loop. Once source 10 receives an RM cell, the ACR value is adjusted. If the congestion bit CI=0 (indicating no congestion), and the No Increase bit NI=0 (indicating increase enabled), the ACR is adjusted as follows: EQU ACR=max(min(PCR,ER,ACR+RIF*PCR),MCR). (2)
If CI=1 (congestion), the ACR value is adjusted as follows: ##EQU2## where RIF is the Rate Increase Factor, RDF is the Rate Decrease Factor, and MCR is the Minimum Cell Rate. Note that the factors RIF and RDF control the rate at which the source increases and decreases its rate, respectively. A good overview of the rate-based scheme is disclosed by F. Bonomi et al., "The Rate-Based Flow Control Framework for the Available Bit Rate ATM Service," IEEE Networks Magazine, pp. 25-39, March-April 1995, which is incorporated by reference herein.
What is needed is an ABR congestion control scheme that provides a fair, fast adaptive rate allocation algorithm designed for ATM switches implementing explicit rate congestion control supporting an ABR service. Further, it is desired that the ABR congestion control scheme provide computational simplicity, fast convergence, oscillation free steady state, high link utilization and low buffer requirements. Further still, the desired ABR congestion control scheme must be robust in the sense that any loss of RM cells does not affect the functionality, or stability of the congestion control scheme.